package leetcode.editor.cn;

public class _79_WordSearch {
    public static void main(String[] args) {
        Solution solution = new _79_WordSearch().new Solution();
        char[][] board = new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        boolean a = solution.exist(board, "ABCCED");
        System.out.println(a);
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        int m, n;
        boolean[][] visited;
        boolean flag = false;
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        public void dfs(char[][] board, String word, int row, int col, int idx) {
            if (idx == word.length() - 1) {
                flag = word.charAt(idx) == board[row][col];
                return;
            }
            if (board[row][col] == word.charAt(idx)) {
                visited[row][col] = true;
                for (int i = 0; i < 4; i++) {
                    int newRow = row + dirs[i][0], newCol = col + dirs[i][1];
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                        dfs(board, word, newRow, newCol, idx + 1);
                        if (flag) return;
                    }
                }
                visited[row][col] = false;
            }
        }

        public boolean exist(char[][] board, String word) {
            m = board.length;
            n = board[0].length;
            visited = new boolean[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dfs(board, word, i, j, 0);
                    if (flag) return true;
                }
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}